import java.util.ArrayList;
import java.util.List;

/**
 * 46. Permutations 全排列
 * https://leetcode.com/problems/permutations/description/
 */
class Permutations {

    /**
     * 方法：使用回溯算法生成所有可能的排列
     * 
     * Args:
     *   nums: 整数数组，包含需要排列的元素
     * 
     * Returns:
     *   List<List<Integer>>: 包含所有可能排列的列表
     * 
     * Time: O(n * n!) - 有n!种排列，每种排列需要O(n)时间复制
     * Space: O(n) - 递归调用栈的深度为n，不考虑输出空间
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, new ArrayList<>(), used, ans);
        return ans;
    }

    /**
     * Level 0: []
     *   Choose 1 → [1] (used=[T,F,F])
     *     Choose 2 → [1,2] (used=[T,T,F])
     *       Choose 3 → [1,2,3] ✅
     *     Choose 3 → [1,3] (used=[T,F,T])
     *       Choose 2 → [1,3,2] ✅
     *   Choose 2 → [2] (used=[F,T,F])
     *     Choose 1 → [2,1] (used=[T,T,F])
     *       Choose 3 → [2,1,3] ✅
     *     Choose 3 → [2,3] (used=[F,T,T])
     *       Choose 1 → [2,3,1] ✅
     *   Choose 3 → [3] (used=[F,F,T])
     *     Choose 1 → [3,1] (used=[T,F,T])
     *       Choose 2 → [3,1,2] ✅
     *     Choose 2 → [3,2] (used=[F,T,T])
     *       Choose 1 → [3,2,1] ✅
     */
    private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                backtrack(nums, path, used, ans);
                path.remove(path.size() - 1); // 回溯
                used[i] = false;              // 回溯
            }
        }
    }

    public List<List<Integer>> permute1(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrace(nums, 0, ans);
        return ans;
    }

    /**
     * 方法：使用回溯算法通过交换元素生成所有排列
     * 
     * Args:
     *   nums: int[] - 需要排列的整数数组
     *   first: int - 当前处理的位置索引
     *   ans: List<List<Integer>> - 存储所有排列结果的列表
     * 
     * Returns:
     *   void - 结果直接存储在ans中
     * 
     * Time: O(n * n!) - 有n!种排列，每种排列需要O(n)时间复制
     * Space: O(n) - 递归调用栈的深度为n
     */
    private void backtrace(int[] nums, int first, List<List<Integer>> ans){
        int n = nums.length;
        if(first == n){
            List<Integer> permutation = new ArrayList<>();
            for(int num : nums) permutation.add(num);
            ans.add(permutation);
            return;
        }
        for(int i = first; i < n; i++){
            swap(nums, first, i);
            backtrace(nums, first + 1, ans);
            swap(nums, first, i);
        }
    }

    private void swap(int nums[], int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}